#include <iostream>
#include "common.h"
using namespace std;
/* 
链表的直接插入排序
 */
int a[] = {1, 4, 7, 2, 5, 8, 3, 6, 9};
void makelist(linklist &l)
{
    l = new lnode;
    l->next = nullptr;
    lnode *r = l, *s;
    for (int i = 0; i < sizeof(a) / sizeof(int); i++)
    {
        s = new lnode;
        s->data = a[i];
        s->next = nullptr;
        r->next = s;
        r = s;
    }
    r = nullptr;
}
// 直接插入排序算法填空题
void inorder(linklist &l)
{
    lnode *p = l->next, *r, *q;
    l->next = nullptr;
    while (p)
    {
        r = p;
        p = p->next;
        q = l;
        while (q->next != nullptr && q->next->data <= r->data)
        {
            q = q->next;
        }
        r->next = q->next;
        q->next = r;
    }
}
int main(int argc, char const *argv[])
{
    linklist l;
    makelist(l);
    printlist(l);
    inorder(l);
    printlist(l);
    return 0;
}
